#ifndef MY_STL_ITERATOR_H
#define MY_STL_ITERATOR_H

#include "type_traits.h"
#include <cstddef>

namespace my_stl {
// 迭代器类别标记
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

// 迭代器基类模板
template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T *, class Reference = T &>
struct iterator {
  using iterator_category = Category;
  using value_type = T;
  using difference_type = Distance;
  using pointer = Pointer;
  using reference = Reference;
};

// 判断是否具有iterator_category类型成员
template <class T> struct has_iterator_cat {
private:
  struct two {char a;char b;};
  template <class U> static two test(...);
  template <class U> static char test(typename U::iterator_category * = 0);

public:
  static const bool value = sizeof(test<T>(0)) == sizeof(char);
};

template <class Iterator, bool> struct iterator_traits_impl {};
// 偏特化
template <class Iterator> struct iterator_traits_impl<Iterator, true> {
  using iterator_category = typename Iterator::iterator_category;
  using value_type = typename Iterator::value_type;
  using difference_type = typename Iterator::difference_type;
  using pointer = typename Iterator::pointer;
  using reference = typename Iterator::reference;
};
//模板萃取辅助器
template <class Iterator, bool> struct iterator_traits_helper 
{};

template <class Iterator>
struct iterator_traits_helper<Iterator, true>: public iterator_traits_impl<
        Iterator,
        std::is_convertible<typename Iterator::iterator_category,input_iterator_tag>::value ||
        std::is_convertible<typename Iterator::iterator_category, output_iterator_tag>::value> {};
//
template <class Iterator> struct iterator_traits : 
  public iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value> {};

// 原生指针的偏特化版本
template <class T> 
struct iterator_traits<T *> {
  using iterator_category = random_access_iterator_tag;
  using value_type = T;
  using difference_type = ptrdiff_t;
  using pointer = T *;
  using reference = T &;
};
// 原生指针的偏特化版本
template <class T> 
struct iterator_traits<const T *> {
  using iterator_category = random_access_iterator_tag;
  using value_type = T;
  using difference_type = ptrdiff_t;
  using pointer =const T *;
  using reference =const T &;
};
/**
 * @brief 用于判断 iterator_traits<T> 萃取出来的迭代器类别是否可转换为指定类型 U 的模板结构体。
 * 
 * @tparam T 待萃取迭代器特性的类型。
 * @tparam U 目标迭代器类别类型，用于判断是否可转换。
 * @tparam has_cat 布尔类型，默认值为 has_iterator_cat<iterator_traits<T>>::value，判断 iterator_traits<T> 是否有 iterator_category 成员。
 */
template <class T, class U, bool = has_iterator_cat<iterator_traits<T>>::value>
struct has_iterator_cat_of
  // 继承自 m_bool_constant，根据 iterator_traits<T> 的 iterator_category 是否可转换为 U 来设置 value
  : public m_bool_constant<std::is_convertible<typename iterator_traits<T>::iterator_category, U>::value>
{
  // 结构体为空，主要使用继承的 m_bool_constant 的 value 成员
};

// 萃取某种迭代器
template <class T, class U>
struct has_iterator_cat_of<T, U, false> : public m_false_type {};

// 是否 严格 属于输入迭代器
template <class Iter>
struct is_exactly_input_iterator : public m_bool_constant<has_iterator_cat_of<Iter, input_iterator_tag>::value && 
    !has_iterator_cat_of<Iter, forward_iterator_tag>::value> {};

template <class Iter>
struct is_input_iterator : public has_iterator_cat_of<Iter, input_iterator_tag> {};

template <class Iter>
struct is_output_iterator : public has_iterator_cat_of<Iter, output_iterator_tag> {};

template <class Iter>
struct is_forward_iterator : public has_iterator_cat_of<Iter, forward_iterator_tag> {};

template <class Iter>
struct is_bidirectional_iterator : public has_iterator_cat_of<Iter, bidirectional_iterator_tag> {};

template <class Iter>
struct is_random_access_iterator : public has_iterator_cat_of<Iter, random_access_iterator_tag> {};

template <class Iter>
struct is_iterator : public m_bool_constant<is_input_iterator<Iter>::value || is_output_iterator<Iter>::value> {};

// 萃取某个迭代器的 category
template <class Iterator>
// 获取迭代器的类别标签 这里用于告诉编译器 iterator_category 是一个类型名
// 而不是一个函数或变量名，从而避免了可能的名称冲突。
typename iterator_traits<Iterator>::iterator_category //函数模板的返回值类型（类似int func() 中的int）
iterator_category(const Iterator&)
{
  using Category = typename iterator_traits<Iterator>::iterator_category;
  return Category();
}
// 萃取某个迭代器的 distance_type
template <class Iterator>
typename iterator_traits<Iterator>::difference_type*
distance_type(const Iterator&)
{
  // 这里返回一个指针，因为 distance_type 是一个指针类型，
  // 用于指示迭代器之间的距离。
  // 这里返回一个空指针，因为我们不需要具体的距离值，只需要知道类型即可。
  return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}
// 以下函数用于计算迭代器间的距离

// distance 的 input_iterator_tag 的版本
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag)
{
  typename iterator_traits<InputIterator>::difference_type n = 0;
  while (first != last)
  {
    ++first;
    ++n;
  }
  return n;
}
// distance 的 random_access_iterator_tag 的版本
template <class RandomIter>
typename iterator_traits<RandomIter>::difference_type
distance_dispatch(RandomIter first, RandomIter last,
                  random_access_iterator_tag)
{
  return last - first;
}
// distance 的函数入口
// 这里使用了 iterator_category 来选择合适的版本
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
  return distance_dispatch(first, last, iterator_category(first));
}
// 以下函数用于让迭代器前进 n 个距离

// advance 的 input_iterator_tag 的版本
template <class InputIterator, class Distance>
void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag)
{
  while (n--) 
    ++i;
}

// advance 的 bidirectional_iterator_tag 的版本
template <class BidirectionalIterator, class Distance>
void advance_dispatch(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)
{
  if (n >= 0)
    while (n--)  ++i;
  else
    while (n++)  --i;
}

// advance 的 random_access_iterator_tag 的版本
template <class RandomIter, class Distance>
void advance_dispatch(RandomIter& i, Distance n, random_access_iterator_tag)
{
  i += n;
}
// advance 的函数入口
// 这里使用了 iterator_category 来选择合适的版本
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n)
{
  advance_dispatch(i, n, iterator_category(i));
}

/*****************************************************************************************/

// 模板类 : reverse_iterator
// 代表反向迭代器，使前进为后退，后退为前进
template <class Iterator>
class reverse_iterator
{
private:
  Iterator current;  // 记录对应的正向迭代器

public:
  // 反向迭代器的五种相应型别
  typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
  typedef typename iterator_traits<Iterator>::value_type        value_type;
  typedef typename iterator_traits<Iterator>::difference_type   difference_type;
  typedef typename iterator_traits<Iterator>::pointer           pointer;
  typedef typename iterator_traits<Iterator>::reference         reference;

  typedef Iterator                                              iterator_type;
  typedef reverse_iterator<Iterator>                            self;

public:
  // 构造函数
  reverse_iterator() {}
  explicit reverse_iterator(iterator_type i) :current(i) {}
  reverse_iterator(const self& rhs) :current(rhs.current) {}

public:
  // 取出对应的正向迭代器
  iterator_type base() const 
  { return current; }

  // 重载操作符
  reference operator*() const
  { // 实际对应正向迭代器的前一个位置
    auto tmp = current;
    return *--tmp;
  }
  pointer operator->() const
  {
    return &(operator*());
  }

  // 前进(++)变为后退(--)
  self& operator++()
  {
    --current;
    return *this;
  }
  self operator++(int)
  {
    self tmp = *this;
    --current;
    return tmp;
  }
  // 后退(--)变为前进(++)
  self& operator--()
  {
    ++current;
    return *this;
  }
  self operator--(int)
  {
    self tmp = *this;
    ++current;
    return tmp;
  }

  self& operator+=(difference_type n)
  {
    current -= n;
    return *this;
  }
  self operator+(difference_type n) const
  {
    return self(current - n);
  }
  self& operator-=(difference_type n)
  {
    current += n;
    return *this;
  }
  self operator-(difference_type n) const
  {
    return self(current + n);
  }

  reference operator[](difference_type n) const
  {
    return *(*this + n);
  }
};


}; // namespace my_stl
#endif